package com.platform.modules.alg.alglib.poj2778;

import java.util.LinkedList;
import java.util.Queue;

public class Poj2778 {
    public static int maxn = 105;
    public static int K = 4; // 代表 A、C、T 和 G
    public static int MOD = 100000;
    public static int root; // 字典树的根
    public static int L; // 字典树节点个数
    public String output = "";
    ACAutomata ac = new ACAutomata();

    // 矩阵乘法
    public static mat mul(mat A, mat B) {
        mat C = new mat();
        for (int i = 0; i < L; i++)
            for (int j = 0; j < L; j++)
                for (int k = 0; k < L; k++)
                    C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % MOD;
        return C;
    }

    // A^n
    public static mat pow(mat A, int n) {
        mat ans = new mat();
        for (int i = 0; i < L; i++)
            ans.a[i][i] = 1; // 单位矩阵
        while (n > 0) {
            if ((n & 1) > 0)
                ans = mul(ans, A);
            A = mul(A, A);
            n >>= 1;
        }
        return ans;
    }

    public String cal(String input) {
        int m; // 病毒数量
        int n; // DNA 序列长度
        String[] line = input.split("\n");
        String[] num = line[0].split(" ");
        m = Integer.parseInt(num[0]);
        n = Integer.parseInt(num[1]);
        int i = 1;
        ac.init();
        while (m-- > 0) {
            ac.insert(line[i++]);
        }
        ac.build();
        output = ac.query(n) + "";
        return output;
    }
}

class mat {
    int a[][] = new int[Poj2778.maxn][Poj2778.maxn];
}

class ACAutomata {
    int next[][] = new int[Poj2778.maxn][Poj2778.K];
    int fail[] = new int[Poj2778.maxn];
    int end[] = new int[Poj2778.maxn]; // 结束标志
    int id[] = new int[Poj2778.maxn];

    int idx(char ch) { // 转化数字
        switch (ch) {
            case 'A':
                return 0;
            case 'C':
                return 1;
            case 'T':
                return 2;
            case 'G':
                return 3;
        }
        return -1;
    }

    int newNode() { // 新建结点
        for (int i = 0; i < Poj2778.K; i++)
            next[Poj2778.L][i] = -1;
        end[Poj2778.L] = 0;
        return Poj2778.L++; // 节点个数新增1
    }

    void init() { // 初始化
        Poj2778.L = 0;
        Poj2778.root = newNode(); // 根是 0 号节点
    }

    void insert(String s) { // 插入一个遗传病片段
        int len = s.length();
        int p = Poj2778.root;
        for (int i = 0; i < len; i++) {
            int ch = idx(s.charAt(i));
            if (next[p][ch] == -1)
                next[p][ch] = newNode();
            p = next[p][ch];
        }
        end[p]++;
    }
    // 构建AC自动机
    void build() {
        Queue<Integer> Q = new LinkedList<>(); // 队列，BFS使用
        fail[Poj2778.root] = Poj2778.root;
        for (int i = 0; i < Poj2778.K; i++) {
            if (next[Poj2778.root][i] == -1) {
                next[Poj2778.root][i] = Poj2778.root;
            } else {
                fail[next[Poj2778.root][i]] = Poj2778.root;
                Q.add(next[Poj2778.root][i]);
            }
        }
        while (!Q.isEmpty()) {
            int now = Q.peek();
            Q.poll();
            if (end[fail[now]] > 0)
                end[now]++; // 重要!!如果当前结点的失败指针end有结束标记，当前结点的 end++
            for (int i = 0; i < Poj2778.K; i++) {
                if (next[now][i] != -1) {
                    fail[next[now][i]] = next[fail[now]][i];
                    Q.add(next[now][i]);
                } else
                    next[now][i] = next[fail[now]][i];
            }
        }
    }

    int query(int n) {
        mat F = new mat();
        int ids = 0;
        for (int i = 0; i < id.length; i++) {
            id[i] = -1;
        }

        for (int i = 0; i < Poj2778.L; i++) // 对未标记的结点重新编号
            if (end[i] == 0)
                id[i] = ids++;
        for (int u = 0; u < Poj2778.L; u++) {
            if (end[u] > 0) continue;
            for (int j = 0; j < Poj2778.K; j++) {
                int v = next[u][j];
                if (end[v] == 0)
                    F.a[id[u]][id[v]]++;
            }
        }
        Poj2778.L = ids;
        F = Poj2778.pow(F, n);
        int res = 0;
        for (int i = 0; i < Poj2778.L; i++)
            res = (res + F.a[0][i]) % Poj2778.MOD;
        return res;
    }
}
